package 单调栈_下;

// 去除重复字母保证剩余字符串的字典序最小
// 给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次
// 需保证 返回结果的字典序最小
// 要求不能打乱其他字符的相对位置
// 测试链接 : https://leetcode.cn/problems/remove-duplicate-letters/

import java.util.Arrays;

public class Code02_RemoveDuplicateLetters {

    public static int MAXN = 26;

    // 每种字符词频统计： a->0, b->1, c->2, 26个位置从0-25代表着：a-z
    // a 3次 -> cnts[0] = 3;
    // e 5次 -> cnts[4] = 5;
    public static int[] cnts = new int[MAXN];

    // a->0, b->1, c->2, 26个位置从0-25代表着：a-z 这些字符是否已经入栈
    public static boolean[] enter = new boolean[MAXN];

    // 单调栈，存的是a-z之中的字符
    public static char[] stack = new char[MAXN];

    public static int r;

    public String removeDuplicateLetters(String str) {
        r = 0;
        char[] chars = str.toCharArray();
        // 每种字符的词频都是0
        Arrays.fill(cnts, 0);
        // 每种字符都没有进过栈
        Arrays.fill(enter, false);
        // 每种字符进行词频统计
        for (char ch : chars) {
            cnts[ch - 'a']++;
        }
        for (char cur : chars) {
            // 从左往右依次遍历字符
            if (!enter[cur - 'a']) { //字符没进过栈
                //栈中的元素，出栈条件，栈顶的字符 > 当前的字符，栈顶的字符的词频 > 0
                while (r > 0 && stack[r - 1] > cur && cnts[stack[r - 1] - 'a'] > 0) {
                    // 栈顶元素出栈，并改为：false
                    enter[stack[--r] - 'a'] = false;
                }
                // 入栈，改为true
                stack[r++] = cur;
                enter[cur - 'a'] = true;
            }
            // 当前字符的词频 -1，以方便判断后面还有没有这种字符
            cnts[cur - 'a']--;
        }
        return String.valueOf(stack, 0, r);
    }
}
